Tags: #◇Computer Science #◇CSOPESY #◇Operating Systems #◇Reviewer #◇Finals #◇Quiz

---

CSOPESY Midterm Mock Exam

◇Cover Sheet

Course: CSOPESY — Operating Systems
Coverage: Weeks 1-8 (Modules 1-3)
Format: Part I — Multiple Choice (25 pts) | Part II — Problem Solving (35 pts) | Total: 60 pts
Instructions: This is a timed mock. Set a timer for 75 minutes before starting. Do not refer to your notes until after completing all sections.

---

---

◇Part I: Problem Solving (35 points)

---

Problem 1: CPU Scheduling (25 pts)

Given the following set of processes:

For each of the following four algorithms, draw the Gantt chart and compute the CT, TAT, WT per process and the Average Waiting Time:

(a) First-Come First-Served (FCFS) — 6 pts

(b) Non-Preemptive Priority Scheduling (lower number = higher priority) — 6 pts

(c) Shortest Remaining Time First (SRTF) — 7 pts

(d) Round Robin with time quantum $q = 2$ — 6 pts

Formulas:
$TAT = CT - AT \qquad WT = TAT - BT \qquad Avg\ WT = \frac{\sum WT_i}{n}$

---

Problem 2: Effective Access Time (5 pts)

A system uses a two-level cache-to-memory hierarchy with the following parameters:

• Cache hit rate: $H = 0.92$
• Cache access time: $T_c = 5$ ns
• Main memory access time: $T_m = 200$ ns
• Access model: Sequential (memory is accessed only on a cache miss, after the cache lookup completes)

(a) Using the EAT formula, compute the Effective Access Time. Show your work. (3 pts)

$EAT = H \times T_c + (1-H) \times (T_c + T_m)$

(b) If the cache hit rate improves to $H = 0.99$, compute the new EAT. (2 pts)

---

Problem 3: Amdahl's Law (5 pts)

A parallel image-processing application is profiled. Analysis reveals that 30% of its execution is inherently sequential (cannot be parallelized — reading input, writing output, and maintaining state). The remaining 70% can be distributed across any number of cores.

(a) Using Amdahl's Law, compute the maximum theoretical speedup with $N = 4$ processor cores. Show your work. (3 pts)

$Speedup \le \frac{1}{S + \frac{1-S}{N}} \qquad \text{where } S = \text{sequential fraction}$

(b) As the number of cores approaches infinity ($N \to \infty$), what is the absolute maximum speedup this application can theoretically achieve? What does this imply about the value of simply adding more cores? (2 pts)

---

---

◇Problem Solving Answer Key

Problem 1 Solutions

Process Table:

---

(a) FCFS

Gantt Chart:

Avg WT: $(0 + 4 + 6 + 13 + 15) / 5 = 38 / 5 = \mathbf{7.6}$ ms

---

(b) Non-Preemptive Priority (1 = Highest)

Selection logic:

• t=0: Only P1 (pri=2) → run P1 (0→6, CT=6)
• t=6: Available: P2(1), P3(4), P4(3), P5(5) — all arrived by t=6. Highest: P2(1) → 6→10
• t=10: Available: P3(4), P4(3), P5(5). Highest: P4(3) → 10→13
• t=13: Available: P3(4), P5(5). Highest: P3(4) → 13→21
• t=21: Only P5(5) → 21→26

Gantt Chart:

Avg WT: $(0 + 4 + 9 + 5 + 15) / 5 = 33 / 5 = \mathbf{6.6}$ ms

---

(c) SRTF (Preemptive SJF)

Event-by-event trace:

Gantt Chart:

Avg WT: $(0 + 7 + 14 + 1 + 7) / 5 = 29 / 5 = \mathbf{5.8}$ ms

---

(d) Round Robin (q = 2)

Queue trace (convention: new arrivals at quantum boundary join before re-queued process):

Gantt Chart:

Avg WT: $(10 + 4 + 14 + 11 + 13) / 5 = 52 / 5 = \mathbf{10.4}$ ms

---

[!note] Algorithm Comparison Summary

Algorithm	Avg WT
SRTF	5.8 ms (best)
Non-Preemptive Priority	6.6 ms
FCFS	7.6 ms
Round Robin (q=2)	10.4 ms

SRTF minimizes average waiting time. RR with a small quantum performs worst here due to high context switch turnover across 5 processes.

---

Problem 2 Solution: EAT

(a) H = 0.92:

$EAT = H \times T_c + (1-H) \times (T_c + T_m)$
$= 0.92 \times 5 + 0.08 \times (5 + 200)$
$= 4.6 + 0.08 \times 205$
$= 4.6 + 16.4 = \mathbf{21.0 \text{ ns}}$

(b) H = 0.99:

$EAT = 0.99 \times 5 + 0.01 \times 205$
$= 4.95 + 2.05 = \mathbf{7.0 \text{ ns}}$

Insight: Improving cache hit rate from 92% to 99% cuts EAT by 67% (21.0 → 7.0 ns), underscoring why CPU designers invest heavily in cache design.

---

Problem 3 Solution: Amdahl's Law

(a) N = 4 cores, S = 0.30:

$Speedup \le \frac{1}{0.30 + \frac{0.70}{4}} = \frac{1}{0.30 + 0.175} = \frac{1}{0.475} \approx \mathbf{2.11x}$

(b) N → ∞:

$Speedup_{max} = \frac{1}{S + 0} = \frac{1}{0.30} \approx \mathbf{3.33x}$

Implication: No matter how many cores are added, the maximum speedup is capped at 3.33x because 30% of the application is sequential and cannot be parallelized. Adding cores beyond a certain point yields negligible returns — the sequential bottleneck becomes the only limiting factor. This is why optimizing the sequential portion (reducing $S$) is often more impactful than simply adding more hardware.

---

◇References & Navigation

• Related Notes: ◇CSOPESY 01 - Introduction, ◇CSOPESY 02 - Operating System Structure, ◇CSOPESY 03 - IO and Display, ◇CSOPESY 04 - Processes, ◇CSOPESY 05 - Threads, ◇CSOPESY 06 - CPU Scheduling, ◇CSOPESY 07 - Synchronization Tools
• Practice Quiz 1: ◇[QZ] CSOPESY Practice Quiz 1 - OS Foundations
• Practice Quiz 2: ◇[QZ] CSOPESY Practice Quiz 2 - CPU Scheduling
• Finals Reviewer: ◇[REV] CSOPESY Comprehensive Finals Reviewer